/**
 * LeetCode 88. 合并两个有序数组
 */
public class Solution_88 {
    /**
     * 从后向前合并
     * <p>
     * 时间复杂度：O(m+n)
     * <p>
     * 空间复杂度：O(1)
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 合并后最后一个元素的索引
        int index = m + n - 1;
        // nums1 和 nums2 最后一个元素的索引
        int p = m - 1, q = n - 1;

        while (p >= 0 && q >= 0) {
            if (nums1[p] > nums2[q]) {
                nums1[index] = nums1[p];
                p--;
            } else {
                nums1[index] = nums2[q];
                q--;
            }
            index--;
        }
        while (p >= 0) {
            nums1[index] = nums1[p];
            p--;
            index--;
        }
        while (q >= 0) {
            nums1[index] = nums2[q];
            q--;
            index--;
        }
    }
}
